package writtenExamination;

import java.util.Arrays;

public class HuaWei3 {
    public static void main(String[] args) {
        int[] nums = {1,2,3,2,5,4};
        int k = 3;
        int n = nums.length;
        // 最大的最小值
        System.out.println(getMaxMinRes(nums,n,k));
        System.out.println(getMaxMinDPRes(nums,n,k));
        // 最小的最大值
        System.out.println(getMinMaxRes(nums,n,k));
        // 按均值分
        System.out.println(getRes(nums,n,k));
    }

    private static String getRes(int[] nums, int n, int k) {
        if (n < k){
            return null;
        }
        int sum = Arrays.stream(nums).sum();
        int ave = sum / (k + 1);
        int s = 0;
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < n; i++) {
            s += nums[i];
            res.append(nums[i]);
            if (s > ave && k > 1){
                res.append("/");
                k --;
                s = 0;
            }
        }
        return res.toString();
    }

    private static int getMaxMinDPRes(int[] nums, int n, int k) {
        if (n < 1){
            return -1;
        }
        if (n < 2){
            return nums[0];
        }

        int[][] dp = new int[n][k + 1];
        Arrays.fill(dp[0],nums[0]);
        for (int i = 1; i < n; i++) {
            Arrays.fill(dp[i],Integer.MAX_VALUE);
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                if (j == 1){
                    dp[i][j] = getSum(nums,0,i);
                    continue;
                }
                for (int l = 0; l < i; l++) {
                    dp[i][j] = Math.min(dp[i][j],Math.max(dp[l][j - 1],getSum(nums,l + 1,i)));
                }
            }
        }
        return dp[n - 1][k];
    }

    private static int getMinMaxRes(int[] nums, int n, int k) {
        if (n == 1){
            if (k > 0){
                return 0;
            }
            return getSum(nums,0,n - 1);
        }
        if (k == 1){
            return getSum(nums,0,n - 1);
        }
        int max = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(max,Math.min(getMinMaxRes(nums,i,k - 1),getSum(nums,i,n - 1)));
        }
        return max;
    }

    private static int getMaxMinRes(int[] nums, int n, int k) {
        if (n == 1){
            return nums[0];
        }
        if (k == 1){
            return getSum(nums,0,n - 1);
        }
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            min = Math.min(min,Math.max(getMaxMinRes(nums,i,k - 1),getSum(nums,i,n - 1)));
        }
        return min;
    }

    private static int getSum(int[] nums, int start, int end) {
        int sum = 0;
        for (int i = start; i <= end; i++) {
            sum += nums[i];
        }
        return sum;
    }
}
